﻿// Write a program that finds in given array of integers a sequence of given sum S (if present). 
// Example: {4, 3, 1, 4, 2, 5, 8}, S=11 -> {4, 2, 5}

using System;

class FindSequenceOfGivenSum
{
    static void Main()
    {
        // read Array Size
        uint arraySize;
        do
        {
            Console.Write("Enter array size: ");
        } while (!uint.TryParse(Console.ReadLine(), out arraySize));

        // read array elements
        int[] intArray = new int[arraySize];
        for (int i = 0; i < intArray.Length; i++)
        {
            do
            {
                Console.Write("Enter array elements {0}: ", i + 1);
            } while (!int.TryParse(Console.ReadLine(), out intArray[i]));
        }

        // read sum (S)
        int searchingSum;
        do
        {
            Console.Write("Enter searching sum (S): ");
        } while (!int.TryParse(Console.ReadLine(), out searchingSum));

        // search sequence of given sum
        int sum = 0;
        int leftMarker = 0;
        int rightMarker = 0;
        bool sumExist = false;

        for (int i = 0; i < intArray.Length; i++)
        {
            for (int j = i; j < intArray.Length; j++)
            {
                // no check for sum > searchingSum so it could work for negative searchingSum
                sum += intArray[j];

                if (sum == searchingSum)
                {
                    leftMarker = i;
                    rightMarker = j;
                    sumExist = true;
                    break;
                }
            }

            if (sum == searchingSum)
            {
                break;
            }
            else
            {
                sum = 0;
            }
        }

        if (sumExist)
        {
            Console.Write("{");
            for (int i = leftMarker; i <= rightMarker; i++)
            {
                Console.Write(intArray[i]);
                if (i != rightMarker)
                {
                    Console.Write(", ");
                }
            }
            Console.WriteLine("}");
        }
        else
        {
            Console.WriteLine("No sequence with the given sum ({0})", searchingSum);
        }
    }
}